package _18_剑指OfferII;

public class _004_剑指OfferII只出现一次的数字 {

    public static void main(String[] args) {

        _004_剑指OfferII只出现一次的数字 v = new _004_剑指OfferII只出现一次的数字();

        int[] ins = {1, 1, 1, 100};
        System.out.println(v.singleNumber(ins));

    }

    // 将所有元素的二进制位全部统计到一个32位的数组中，然后对所有二进制对三取余
    // 再将所有二进制位组合起来，剩下的就是只出现一次的数字
    public int singleNumber(int[] nums) {
        int[] bits = new int[32];

        for (int num : nums) {
            int cur = num;
            int count = 0;
            while (cur != 0) {
                if ((cur & 1) == 1) {
                    bits[count]++;
                }
                count++;
                cur >>>= 1;
            }
        }
        // 组合成二进制数, 对于不同位数的二进制位，可以使用|把其组合起来
        int total = 0;
        for (int i = bits.length - 1; i >= 0; i--) {
            total |= bits[i] % 3 << i;
        }
        return total;
    }

}
